{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Absolute Difference Between Elements With Constraint"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #ordered-set"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #有序集合"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minAbsoluteDifference"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #限制条件下元素之间的最小绝对差"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;和一个整数&nbsp;<code>x</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你找到数组中下标距离至少为 <code>x</code>&nbsp;的两个元素的 <strong>差值绝对值</strong>&nbsp;的 <strong>最小值</strong>&nbsp;。</p>\n",
    "\n",
    "<p>换言之，请你找到两个下标&nbsp;<code>i</code> 和&nbsp;<code>j</code>&nbsp;，满足&nbsp;<code>abs(i - j) &gt;= x</code> 且&nbsp;<code>abs(nums[i] - nums[j])</code>&nbsp;的值最小。</p>\n",
    "\n",
    "<p>请你返回一个整数，表示下标距离至少为 <code>x</code>&nbsp;的两个元素之间的差值绝对值的 <strong>最小值</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>示例 1：</b></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [4,3,2,4], x = 2\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>我们选择 nums[0] = 4 和 nums[3] = 4 。\n",
    "它们下标距离满足至少为 2 ，差值绝对值为最小值 0 。\n",
    "0 是最优解。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [5,3,2,10,15], x = 1\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>我们选择 nums[1] = 3 和 nums[2] = 2 。\n",
    "它们下标距离满足至少为 1 ，差值绝对值为最小值 1 。\n",
    "1 是最优解。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,2,3,4], x = 3\n",
    "<b>输出：</b>3\n",
    "<strong>解释：</strong>我们选择 nums[0] = 1 和 nums[3] = 4 。\n",
    "它们下标距离满足至少为 3 ，差值绝对值为最小值 3 。\n",
    "3 是最优解。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>0 &lt;= x &lt; nums.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-absolute-difference-between-elements-with-constraint](https://leetcode.cn/problems/minimum-absolute-difference-between-elements-with-constraint/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-absolute-difference-between-elements-with-constraint](https://leetcode.cn/problems/minimum-absolute-difference-between-elements-with-constraint/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,3,2,4]\\n2', '[5,3,2,10,15]\\n1', '[1,2,3,4]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import  *\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        res = []\n",
    "        n=len(nums)\n",
    "        ans = max(nums)\n",
    "        res = [nums[-1]]\n",
    "        for i in range(n-x-1,-1,-1):\n",
    "            ids = bisect_left(res, nums[i])\n",
    "            print(ids)\n",
    "            if ids < n-x-i:\n",
    "                ans = min([ans,abs(res[ids] - nums[i]),abs(res[ids-1] - nums[i])])\n",
    "            else:\n",
    "                ans = min([ans,  abs(res[ids - 1] - nums[i])])\n",
    "            ids = bisect_left(res, nums[i+x-1])\n",
    "            res.insert(ids,nums[i+x-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: list[int], x: int) -> int:\n",
    "        # minimums = []\n",
    "        # for i in range(len(nums)):\n",
    "        #     if i + x == len(nums):\n",
    "        #         break\n",
    "        #     curr = nums[i]\n",
    "        #     minComp = min([abs(n-curr) for n in nums[i+x:]])\n",
    "        #     minimums.append(minComp)\n",
    "        # return min(minimums)\n",
    "        if x==0:\n",
    "            return 0\n",
    "        \n",
    "        def findByBinarySearch(num, l:list, left=0, right=-10):\n",
    "            if right == -10:\n",
    "                right = len(l) - 1\n",
    "            if left - right > 0:\n",
    "                if right < 0:\n",
    "                    return abs(l[left] - num)\n",
    "                elif left >= len(l):\n",
    "                    return abs(l[right] - num)\n",
    "                else:\n",
    "                    return min(abs(l[left] - num), abs(l[right] - num))\n",
    "            mid = (left + right) // 2\n",
    "            if l[mid] < num:\n",
    "                left = mid + 1\n",
    "                return findByBinarySearch(num, l, left, right)\n",
    "            elif l[mid] > num:\n",
    "                right = mid - 1\n",
    "                return findByBinarySearch(num, l, left, right)\n",
    "            else:\n",
    "                return 0\n",
    "\n",
    "\n",
    "\n",
    "        sortedList = sorted(nums[x:])\n",
    "        minimums = []\n",
    "        for i in range(len(nums)):\n",
    "            if i + x == len(nums):\n",
    "                break\n",
    "            curr = nums[i]\n",
    "            comp = findByBinarySearch(curr, sortedList)\n",
    "            if comp == 0:\n",
    "                return comp\n",
    "            minimums.append(comp)\n",
    "            sortedList.remove(nums[i+x])\n",
    "        return min(minimums)\n",
    "            \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "二分法\n",
    "先初始化res=nums[-1]\n",
    "每次通过二分法想res中插入新元素，同时用二分法查找最相近的元素\n",
    "'''\n",
    "from bisect import  *\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        res = []\n",
    "        n=len(nums)\n",
    "        ans = max(nums)\n",
    "        res = [nums[-1]]\n",
    "        for i in range(n-x-1,-1,-1):\n",
    "            ids = bisect_left(res, nums[i])\n",
    "            print(ids)\n",
    "            if ids < n-x-i:\n",
    "                ans = min([ans,abs(res[ids] - nums[i]),abs(res[ids-1] - nums[i])])\n",
    "            else:\n",
    "                ans = min([ans,  abs(res[ids - 1] - nums[i])])\n",
    "            ids = bisect_left(res, nums[i+x-1])\n",
    "            res.insert(ids,nums[i+x-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 可以不用sortedcontainers只用bisect\n",
    "import bisect\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        j = x\n",
    "        mn = float('inf')\n",
    "        sl = []\n",
    "\n",
    "        while j < n:\n",
    "            bisect.insort(sl,nums[i])\n",
    "            idxj = bisect.bisect(sl, nums[j])\n",
    "\n",
    "            if idxj == 0:\n",
    "                mn = min(mn, abs(nums[j] -  sl[0]))\n",
    "            elif idxj == len(sl):\n",
    "                mn = min(mn, abs(nums[j] - sl[-1]))\n",
    "            else:\n",
    "                mn = min(mn, abs(nums[j] - sl[idxj]), abs(nums[j] - sl[idxj-1]))\n",
    "\n",
    "            i += 1\n",
    "            j += 1\n",
    "\n",
    "        return mn \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        s = []\n",
    "        n = len(nums)\n",
    "        ans = inf\n",
    "        for i in range(x,n):\n",
    "            # 重点一: 有序列表中永远只存在满足距离的元素\n",
    "            # 重点二: 枚举只考虑左侧元素,而不是双向考虑.\n",
    "            bisect.insort(s, nums[i-x])\n",
    "            pos = bisect.bisect_left(s, nums[i])\n",
    "            # 重点三: 只考虑有序列表中,枚举元素的左边和自己\n",
    "            if 0<=pos - 1<len(s):\n",
    "                j = pos -1\n",
    "                ans = min(ans, abs(s[j]-nums[i]))\n",
    "            if 0<= pos <len(s):\n",
    "                j = pos\n",
    "                ans = min(ans, abs(s[j]-nums[i]))\n",
    "                    \n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        \n",
    "        \n",
    "        min_diff = float('inf')\n",
    "        pre_sortednums = [float('-inf'), float('inf')]\n",
    "        for i in range(x, len(nums)):\n",
    "            bisect.insort_left(pre_sortednums, nums[i-x])\n",
    "            min_index = bisect.bisect_left(pre_sortednums, nums[i])\n",
    "            min_diff = min(min_diff, abs(nums[i] - pre_sortednums[min_index]), abs(nums[i]-pre_sortednums[min_index-1]))\n",
    "            # print(i, nums[i],nums[i-x], pre_sortednums, min_diff)\n",
    "\n",
    "            if min_diff == 0:\n",
    "                return 0\n",
    "        \n",
    "        return min_diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left, insort_left\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        ans = float('inf') # 最小值初始化\n",
    "        pre = [float('inf')] # 维护前 i 个数的升序排列，添加了一个初始值防索引不合法\n",
    "        for i in range(len(nums)-x):\n",
    "            insort_left(pre, nums[i]) # 二分插入第 i 个数\n",
    "            \n",
    "            index = bisect_left(pre, nums[i+x]) # 用二分找出后面第 i + x 个数在 pre 中的位置，它和pre中所有数的坐标都是合法的  \n",
    "            tmp = min(abs(pre[index]-nums[i+x]) for index in (index, index-1)) # 找到之后，求附近两个数的绝对值更小的。 比如 现在pre是 [1,9,15], 8 要和 1 9 共同比较，确定绝对值更小的数\n",
    "            ans = min(ans, tmp) #更新最小值\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        s = list()\n",
    "        a = sys.maxsize\n",
    "        for i in range(x, len(nums)):\n",
    "            bisect.insort(s, nums[i-x])\n",
    "            idx = bisect.bisect_left(s, nums[i])\n",
    "            if idx-1 >= 0:\n",
    "                a = min(a, abs(s[idx-1]-nums[i]))\n",
    "            if idx < len(s) and idx >= 0:\n",
    "                a = min(a, abs(s[idx]-nums[i]))\n",
    "            \n",
    "        return a\n",
    "            \n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        index = dict()\n",
    "        q = []\n",
    "        ret = abs(nums[0] - nums[-1])\n",
    "        \n",
    "        n = len(nums)\n",
    "        for i in range(x, n):\n",
    "            loc = bisect.bisect(q, nums[i - x])\n",
    "            q.insert(loc, nums[i - x])\n",
    "            loc = bisect.bisect(q, nums[i])\n",
    "            if loc > 0:\n",
    "                ret = min(ret, abs(q[loc - 1] - nums[i]))\n",
    "            if loc < len(q):\n",
    "                ret = min(ret, abs(q[loc] - nums[i]))\n",
    "            \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        from bisect import bisect_left, insort\n",
    "        stack, res = [], float('inf')\n",
    "\n",
    "        for i in range(x, len(nums)):\n",
    "            insort(stack, nums[i - x])\n",
    "            idx = bisect_left(stack, nums[i])\n",
    "\n",
    "            if idx == 0:\n",
    "                res = min(res, stack[0] - nums[i])\n",
    "            elif idx == len(stack):\n",
    "                res = min(res, nums[i] - stack[-1])\n",
    "            else:\n",
    "                res = min(res, nums[i] - stack[idx - 1], stack[idx] - nums[i])\n",
    "            \n",
    "            if res == 0: return 0\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        res,n = inf,len(nums)\n",
    "        L = [nums[-1]]\n",
    "        l = 1\n",
    "        for i in range(n-x-1,-1,-1):\n",
    "            N = nums[i]\n",
    "            pos = bisect_left(L,N)\n",
    "            if pos < l:res = min(L[pos]-N,res)\n",
    "            if pos > 0:res = min(N-L[pos-1],res)\n",
    "            npos = bisect_left(L,nums[i+x-1])\n",
    "            L.insert(npos,nums[i+x-1])\n",
    "            l += 1\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        ls = SortedList()\n",
    "        res = inf\n",
    "        j = 0\n",
    "        ls.add(nums[j])\n",
    "        j += 1\n",
    "        for i in range(x, n):\n",
    "            k = ls.bisect_left(nums[i])\n",
    "            if k < len(ls):\n",
    "                res = min(res, abs(ls[k] - nums[i]))\n",
    "            if k > 0:\n",
    "                res = min(res, abs(ls[k - 1] - nums[i]))\n",
    "            if j < n:\n",
    "                ls.add(nums[j])\n",
    "                j += 1\n",
    "        return -1 if res == inf else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left, insort_left\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums, x: int) -> int:\n",
    "        ans = float('inf') # 最小值初始化\n",
    "        pre = [float('inf')] # 维护前 i 个数的升序排列，添加了一个初始值防索引不合法\n",
    "        for i in range(len(nums)-x):\n",
    "            insort_left(pre, nums[i]) # 二分插入第 i 个数\n",
    "            \n",
    "            index = bisect_left(pre, nums[i+x]) # 用二分找出后面第 i + x 个数在 pre 中的位置，它和pre中所有数的坐标都是合法的  \n",
    "            tmp = min(abs(pre[index]-nums[i+x]) for index in (index, index-1)) # 找到之后，求附近两个数的绝对值更小的。 比如 现在pre是 [1,9,15], 8 要和 1 9 共同比较，确定绝对值更小的数\n",
    "            ans = min(ans, tmp) #更新最小值\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums, x: int) -> int:\n",
    "        ans = float('inf') # 最小值初始化\n",
    "        pre = [float('inf')] # 维护前 i 个数的升序排列，添加了一个初始值防索引不合法\n",
    "        for i in range(len(nums)-x):\n",
    "            insort_left(pre, nums[i]) # 二分插入第 i 个数\n",
    "            \n",
    "            index = bisect_left(pre, nums[i+x]) # 用二分找出后面第 i + x 个数在 pre 中的位置，它和pre中所有数的坐标都是合法的  \n",
    "            tmp = min(abs(pre[index]-nums[i+x]) for index in (index, index-1)) # 找到之后，求附近两个数的绝对值更小的。 比如 现在pre是 [1,9,15], 8 要和 1 9 共同比较，确定绝对值更小的数\n",
    "            ans = min(ans, tmp) #更新最小值\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from cmath import inf\n",
    "from typing import List\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        answer = inf\n",
    "        sl = SortedList([-inf, inf])\n",
    "\n",
    "        for i in range(x, n):\n",
    "            sl.add(nums[i - x])\n",
    "\n",
    "            j = sl.bisect_left(nums[i])\n",
    "            answer = min(answer, sl[j] - nums[i], nums[i] - sl[j - 1])\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        from bisect import bisect_left, insort\n",
    "        stack, res = [float('-inf'), float('inf')], float('inf')\n",
    "\n",
    "        for i in range(x, len(nums)):\n",
    "            insort(stack, nums[i - x])\n",
    "            idx = bisect_left(stack, nums[i])\n",
    "            res = min(res, nums[i] - stack[idx - 1], stack[idx] - nums[i])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        if x == 0:\n",
    "            return 0 \n",
    "        sl = SortedList((float('-inf'), float('inf')))\n",
    "        ans = float('inf')\n",
    "        n = len(nums)\n",
    "        for i in range(n-1-x, -1, -1):\n",
    "            sl.add(nums[i+x]) \n",
    "            j = sl.bisect_left(nums[i])\n",
    "            ans = min(ans, sl[j] - nums[i], nums[i] - sl[j-1]) \n",
    "        return ans \n",
    "\n",
    "             \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        ans=float(\"inf\")\n",
    "\n",
    "        pre=[float(\"inf\")]\n",
    "        n=len(nums)\n",
    "        for i in range(n-x):\n",
    "            bisect.insort_left(pre,nums[i])\n",
    "\n",
    "            index=bisect.bisect_left(pre,nums[i+x])\n",
    "            s=min(abs(nums[i+x]-pre[index]),abs(nums[i+x]-pre[index-1]))\n",
    "            ans=min(ans,s)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = inf\n",
    "        arr = [nums[-1]]\n",
    "        i = n - x - 1\n",
    "        j = -1\n",
    "        while i >= 0:\n",
    "            y = nums[i]\n",
    "            k = bisect_left(arr, y)\n",
    "            # print(arr, k)\n",
    "            if k < len(arr):\n",
    "                ans = min(ans, abs(y - arr[k]))\n",
    "            if k > 0:\n",
    "                ans = min(ans, abs(y- arr[k - 1]))\n",
    "            if ans == 0:\n",
    "                return ans\n",
    "            # print(arr, k, y, ans)\n",
    "            j -= 1\n",
    "            bisect.insort(arr, nums[j])\n",
    "            i -= 1\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        # 似乎就是个细节注意的 复杂度呢\n",
    "        # 选取i 的右边 x 以后的所有元素并排序\n",
    "        # 通过二分来找最小差\n",
    "        # 右移动 并弹出元素，时间消耗是nlogn # \n",
    "        if x==0:\n",
    "            return 0\n",
    "        n  = len(nums)\n",
    "        ans = inf\n",
    "        left = [-inf, inf]\n",
    "        for i in range(n-x):\n",
    "            # put nums[i] into left\n",
    "            p = bisect_left(left, nums[i])\n",
    "            if nums[i]!=left[p]:\n",
    "                bisect.insort(left, nums[i])\n",
    "            # search nums[i+x]\n",
    "            p = bisect_left(left, nums[i+x])\n",
    "            ans = min(ans, nums[i+x]- left[p-1] )\n",
    "            ans = min(ans, left[p] - nums[i+x])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "\n",
    "    def bi_search(self,start,end,key):\n",
    "        if start==end:\n",
    "            return self.sl[start]\n",
    "        if end-start==1:\n",
    "            abs_end=abs(self.sl[end]-key)\n",
    "            abs_start=abs(self.sl[start]-key)\n",
    "            return self.sl[start] if abs_start<abs_end else self.sl[end]\n",
    "\n",
    "        mid=(start+end)//2\n",
    "        if key==self.sl[mid]:\n",
    "            return self.sl[mid]\n",
    "        elif key>self.sl[mid]:\n",
    "            return self.bi_search(mid,end,key)\n",
    "        else:\n",
    "            return self.bi_search(start,mid,key)\n",
    "\n",
    "    def minAbsoluteDifference(self,nums: List[int], x: int) -> int:\n",
    "        # use binary search tree/ sorted container\n",
    "\n",
    "        min_diff=float('inf')\n",
    "        self.sl=SortedList()\n",
    "        for idx,num in enumerate(nums):\n",
    "            if idx-x<0:\n",
    "                continue\n",
    "            self.sl.add(nums[idx-x])\n",
    "            key=self.bi_search(0,len(self.sl)-1,num)\n",
    "            min_diff=min(abs(num-key),min_diff)\n",
    "        return min_diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        if x == 0: return 0\n",
    "        MX = 10**10 + 7\n",
    "        ans = MX\n",
    "        arr = []\n",
    "        for i, num in enumerate(nums):\n",
    "            idx = bisect.bisect_left(arr, num)\n",
    "            l = arr[idx - 1] if idx else MX\n",
    "            r = arr[idx] if idx < len(arr) else MX\n",
    "            ans = min(ans, min(abs(num - l), abs(num - r)))\n",
    "            if i >= x - 1:\n",
    "                bisect.insort(arr, nums[i - x + 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "from math import inf\n",
    "from typing import List\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        res = inf\n",
    "        left_sort = SortedList([-inf, inf])\n",
    "        for left, right in zip(nums, nums[x:]):\n",
    "            left_sort.add(left)\n",
    "\n",
    "            pos = bisect.bisect_left(left_sort, right)\n",
    "            res = min(res, abs(right - left_sort[pos - 1]), abs(left_sort[pos] - right))\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        s = SortedList()\n",
    "        n = len(nums)\n",
    "        ans = float('inf')\n",
    "        for i in range(x, n):\n",
    "            s.add(nums[i-x])\n",
    "            pos = s.bisect_left(nums[i])\n",
    "            for j in range(pos-1, pos+1):\n",
    "                if 0 <= j < len(s):\n",
    "                    ans = min(ans, abs(nums[i] - s[j]))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        if x == 0:\n",
    "            return 0\n",
    "        \n",
    "        sl = SortedList()\n",
    "        ans = abs(nums[-1] - nums[0])\n",
    "        for i in range(x, len(nums)):\n",
    "            sl.add(nums[i - x])\n",
    "            idx = sl.bisect_left(nums[i])\n",
    "            if idx != len(sl):\n",
    "                ans = min(ans, abs(nums[i] - sl[idx]))\n",
    "            if idx - 1 != -1:\n",
    "                ans = min(ans, abs(nums[i] - sl[idx - 1]))\n",
    "            if ans == 0:\n",
    "                break\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, A: List[int], k: int) -> int:\n",
    "        sl = SortedList([-inf, inf])    # 放两个哨兵\n",
    "        n, res = len(A), inf\n",
    "        for i in range(k, n):\n",
    "            sl.add(A[i - k])\n",
    "            j = sl.bisect_left(A[i])\n",
    "            res = min(res, abs(A[i] - sl[j - 1]), abs(A[i] - sl[j]))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        sl = SortedList([-inf, inf])    # 放两个哨兵\n",
    "        n, res = len(nums), inf\n",
    "        for i in range(x, n):\n",
    "            sl.add(nums[i - x])\n",
    "            j = sl.bisect_left(nums[i])\n",
    "            res = min(res, abs(nums[i] - sl[j - 1]), abs(nums[i] - sl[j]))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums) \n",
    "        sl = SortedList()\n",
    "        ans = inf\n",
    "        now = 0\n",
    "        for i in range(x, n) :\n",
    "            sl.add(nums[now])\n",
    "            index = bisect_left(sl, nums[i]) \n",
    "            if index > 0 :\n",
    "                ans = min(ans, abs(nums[i] - sl[index - 1]))\n",
    "            if index <= now :\n",
    "                ans = min(ans, abs(sl[index] - nums[i]))\n",
    "            now += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "class Solution:\n",
    "  def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "    sl = SortedList([inf, -inf])\n",
    "    res = inf\n",
    "    for i in range(x, len(nums)):\n",
    "      # print(i)\n",
    "      sl.add(nums[i - x])\n",
    "      p = sl.bisect_left(nums[i])\n",
    "      # print(p)\n",
    "      t = min(nums[i] - sl[p - 1], sl[p] - nums[i])\n",
    "      res = min(res, t)\n",
    "    return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, s: List[int], x: int) -> int:\n",
    "        sl = SortedList()\n",
    "        m = 0\n",
    "        n = len(s)\n",
    "        ans = sys.maxsize\n",
    "        for i in range(n):\n",
    "            if i >= x:\n",
    "                sl.add(s[i - x])\n",
    "                m += 1\n",
    "            idx = sl.bisect_left(s[i])\n",
    "            if idx > 0:\n",
    "                ans = min(ans, abs(s[i] - sl[idx - 1]))\n",
    "            if idx < m:\n",
    "                ans = min(ans, abs(s[i] - sl[idx]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        a = SortedList()\n",
    "        j = 0\n",
    "        n = len(nums)\n",
    "        ans = inf\n",
    "        for i in range(n):\n",
    "            while j < n and i - x >= j:\n",
    "                a.add(nums[j])\n",
    "                j += 1\n",
    "            ind = a.bisect_left(nums[i])\n",
    "            for k in [ind - 1, ind]:\n",
    "                if k >= 0 and k < len(a):\n",
    "                    ans = min(ans, abs(nums[i] - a[k]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        left = SortedList()\n",
    "        ans = float('inf')\n",
    "        n  = len(nums)\n",
    "        for i in range(n):\n",
    "            if i>=x:\n",
    "                left.add(nums[i-x])\n",
    "                #print(left,i)\n",
    "            j = left.bisect_left(nums[i])\n",
    "            for k in [j-1,j]:\n",
    "                if 0<=k<len(left):\n",
    "                    #print('d',left,k)\n",
    "                    ans = min(ans, abs(left[k]-nums[i]))\n",
    "        return ans\n",
    "                    \n",
    "                \n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        n=len(nums)\n",
    "        s=SortedList()\n",
    "        ans=9999999999\n",
    "        for i in range(x,n):\n",
    "            s.add(nums[i])\n",
    "        for i in range(n-x):\n",
    "            temp=bisect_left(s,nums[i])\n",
    "            if temp<len(s):\n",
    "                ans=min(ans,abs(s[temp]-nums[i]))\n",
    "            if temp-1>=0:\n",
    "                ans=min(ans,abs(s[temp-1]-nums[i]))\n",
    "            s.remove(nums[i+x])\n",
    "        return ans\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], k: int) -> int:\n",
    "        from sortedcontainers import SortedList\n",
    "        lst = SortedList()\n",
    "        ret = inf\n",
    "        j = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            while j < n and j <= i - k:\n",
    "                lst.add(nums[j])\n",
    "                j += 1\n",
    "            idx = lst.bisect_left(nums[i])\n",
    "            for k in [idx-1, idx, idx+1]:\n",
    "                if 0 <= k < len(lst) and abs(lst[k] - nums[i]) < ret:\n",
    "                    ret = abs(lst[k] - nums[i])\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], k: int) -> int:\n",
    "        from sortedcontainers import SortedList\n",
    "        ret = inf\n",
    "        lst = SortedList([-inf, inf])\n",
    "        for x, y in zip(nums, nums[k:]):\n",
    "            lst.add(x)\n",
    "            cur = lst.bisect_left(y)\n",
    "            ret = min(ret, lst[cur]-y, y-lst[cur-1])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        h = SortedList()\n",
    "        ans = inf\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            h.add(nums[i])\n",
    "            if i - k >= 0:\n",
    "                t = nums[i - k]\n",
    "                idx = bisect_right(h, t)\n",
    "                if idx != len(h):\n",
    "                    \n",
    "                    ans = min(ans, abs(t - h[idx]))\n",
    "                if idx != 0:\n",
    "                    \n",
    "                    ans = min(ans, abs(t - h[idx - 1]))\n",
    "        return ans\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        l=SortedList()\n",
    "        res=inf\n",
    "        for i in range(len(nums)-1, -1, -1):\n",
    "            l.add(nums[i])\n",
    "            if i-x>=0:\n",
    "                idx=bisect_left(l,nums[i-x])\n",
    "                for j in (idx-1,idx,idx+1):\n",
    "                    if 0<=j<len(l):\n",
    "                        res=min(res,abs(nums[i-x]-l[j]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        if x == 0:\n",
    "            return 0\n",
    "        from sortedcontainers import SortedList\n",
    "        s = SortedList(nums[x:])\n",
    "        ans = inf\n",
    "        for j, y in enumerate(nums[:-x]):\n",
    "            i = bisect_left(s, y)\n",
    "            if i == len(s):\n",
    "                ans = min(ans, abs(y - s[-1]))\n",
    "            else:\n",
    "                ans = min(ans, abs(y - s[i]))\n",
    "                if i > 0:\n",
    "                    ans = min(ans, abs(y - s[i - 1]))\n",
    "            s.remove(nums[j + x])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        h = SortedList()\n",
    "        ans = inf\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            h.add(nums[i])\n",
    "            if i - k >= 0:\n",
    "                t = nums[i - k]\n",
    "                idx = bisect_right(h, t)\n",
    "                if idx != len(h):\n",
    "                    \n",
    "                    ans = min(ans, abs(t - h[idx]))\n",
    "                if idx != 0:\n",
    "                    \n",
    "                    ans = min(ans, abs(t - h[idx - 1]))\n",
    "        return ans\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Multiset  --从小到大排序\n",
    "class SortedList:\n",
    "    def __init__(self, iterable=(), _load=200):\n",
    "        values = sorted(iterable)\n",
    "        self._len = _len = len(values)\n",
    "        self._load = _load\n",
    "        self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]\n",
    "        self._list_lens = [len(_list) for _list in _lists]\n",
    "        self._mins = [_list[0] for _list in _lists]\n",
    "        self._fen_tree = []\n",
    "        self._rebuild = True\n",
    "\n",
    "    def _fen_build(self):\n",
    "        \"\"\"红黑树\"\"\"\n",
    "        self._fen_tree[:] = self._list_lens\n",
    "        _fen_tree = self._fen_tree\n",
    "        for i in range(len(_fen_tree)):\n",
    "            if i | i + 1 < len(_fen_tree):\n",
    "                _fen_tree[i | i + 1] += _fen_tree[i]\n",
    "        self._rebuild = False\n",
    "\n",
    "    def _fen_update(self, index, value):\n",
    "        \"\"\"更新索引为index的值\"\"\"\n",
    "        if not self._rebuild:\n",
    "            _fen_tree = self._fen_tree\n",
    "            while index < len(_fen_tree):\n",
    "                _fen_tree[index] += value\n",
    "                index |= index + 1\n",
    "\n",
    "    def _fen_query(self, end):\n",
    "        \"\"\"返回总和\"\"\"\n",
    "        if self._rebuild:\n",
    "            self._fen_build()\n",
    "\n",
    "        _fen_tree = self._fen_tree\n",
    "        x = 0\n",
    "        while end:\n",
    "            x += _fen_tree[end - 1]\n",
    "            end &= end - 1\n",
    "        return x\n",
    "\n",
    "    def _fen_findkth(self, k):\n",
    "        \"\"\"返回区间第k大的值\"\"\"\n",
    "        _list_lens = self._list_lens\n",
    "        if k < _list_lens[0]:\n",
    "            return 0, k\n",
    "        if k >= self._len - _list_lens[-1]:\n",
    "            return len(_list_lens) - 1, k + _list_lens[-1] - self._len\n",
    "        if self._rebuild:\n",
    "            self._fen_build()\n",
    "\n",
    "        _fen_tree = self._fen_tree\n",
    "        idx = -1\n",
    "        for d in reversed(range(len(_fen_tree).bit_length())):\n",
    "            right_idx = idx + (1 << d)\n",
    "            if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:\n",
    "                idx = right_idx\n",
    "                k -= _fen_tree[idx]\n",
    "        return idx + 1, k\n",
    "\n",
    "    def _delete(self, pos, idx):\n",
    "        \"\"\"Delete value at the given `(pos, idx)`.\"\"\"\n",
    "        _lists = self._lists\n",
    "        _mins = self._mins\n",
    "        _list_lens = self._list_lens\n",
    "\n",
    "        self._len -= 1\n",
    "        self._fen_update(pos, -1)\n",
    "        del _lists[pos][idx]\n",
    "        _list_lens[pos] -= 1\n",
    "\n",
    "        if _list_lens[pos]:\n",
    "            _mins[pos] = _lists[pos][0]\n",
    "        else:\n",
    "            del _lists[pos]\n",
    "            del _list_lens[pos]\n",
    "            del _mins[pos]\n",
    "            self._rebuild = True\n",
    "\n",
    "    def _loc_left(self, value):\n",
    "        \"\"\"Return an index pair that corresponds to the first position of `value` in the sorted list.\"\"\"\n",
    "        if not self._len:\n",
    "            return 0, 0\n",
    "\n",
    "        _lists = self._lists\n",
    "        _mins = self._mins\n",
    "\n",
    "        lo, pos = -1, len(_lists) - 1\n",
    "        while lo + 1 < pos:\n",
    "            mi = (lo + pos) >> 1\n",
    "            if value <= _mins[mi]:\n",
    "                pos = mi\n",
    "            else:\n",
    "                lo = mi\n",
    "\n",
    "        if pos and value <= _lists[pos - 1][-1]:\n",
    "            pos -= 1\n",
    "\n",
    "        _list = _lists[pos]\n",
    "        lo, idx = -1, len(_list)\n",
    "        while lo + 1 < idx:\n",
    "            mi = (lo + idx) >> 1\n",
    "            if value <= _list[mi]:\n",
    "                idx = mi\n",
    "            else:\n",
    "                lo = mi\n",
    "\n",
    "        return pos, idx\n",
    "\n",
    "    def _loc_right(self, value):\n",
    "        \"\"\"Return an index pair that corresponds to the last position of `value` in the sorted list.\"\"\"\n",
    "        if not self._len:\n",
    "            return 0, 0\n",
    "\n",
    "        _lists = self._lists\n",
    "        _mins = self._mins\n",
    "\n",
    "        pos, hi = 0, len(_lists)\n",
    "        while pos + 1 < hi:\n",
    "            mi = (pos + hi) >> 1\n",
    "            if value < _mins[mi]:\n",
    "                hi = mi\n",
    "            else:\n",
    "                pos = mi\n",
    "\n",
    "        _list = _lists[pos]\n",
    "        lo, idx = -1, len(_list)\n",
    "        while lo + 1 < idx:\n",
    "            mi = (lo + idx) >> 1\n",
    "            if value < _list[mi]:\n",
    "                idx = mi\n",
    "            else:\n",
    "                lo = mi\n",
    "\n",
    "        return pos, idx\n",
    "\n",
    "    def add(self, value):\n",
    "        \"\"\"添加元素\"\"\"\n",
    "        _load = self._load\n",
    "        _lists = self._lists\n",
    "        _mins = self._mins\n",
    "        _list_lens = self._list_lens\n",
    "\n",
    "        self._len += 1\n",
    "        if _lists:\n",
    "            pos, idx = self._loc_right(value)\n",
    "            self._fen_update(pos, 1)\n",
    "            _list = _lists[pos]\n",
    "            _list.insert(idx, value)\n",
    "            _list_lens[pos] += 1\n",
    "            _mins[pos] = _list[0]\n",
    "            if _load + _load < len(_list):\n",
    "                _lists.insert(pos + 1, _list[_load:])\n",
    "                _list_lens.insert(pos + 1, len(_list) - _load)\n",
    "                _mins.insert(pos + 1, _list[_load])\n",
    "                _list_lens[pos] = _load\n",
    "                del _list[_load:]\n",
    "                self._rebuild = True\n",
    "        else:\n",
    "            _lists.append([value])\n",
    "            _mins.append(value)\n",
    "            _list_lens.append(1)\n",
    "            self._rebuild = True\n",
    "\n",
    "    def discard(self, value):\n",
    "        \"\"\"如果“value”存在，则从排序列表中删除它\"\"\"\n",
    "        _lists = self._lists\n",
    "        if _lists:\n",
    "            pos, idx = self._loc_right(value)\n",
    "            if idx and _lists[pos][idx - 1] == value:\n",
    "                self._delete(pos, idx - 1)\n",
    "\n",
    "    def remove(self, value):\n",
    "        \"\"\"从排序列表中删除`value``值`必须存在。\"\"\"\n",
    "        _len = self._len\n",
    "        self.discard(value)\n",
    "        if _len == self._len:\n",
    "            raise ValueError('{0!r} not in list'.format(value))\n",
    "\n",
    "    def pop(self, index=-1):\n",
    "        \"\"\"删除第index个元素\"\"\"\n",
    "        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)\n",
    "        value = self._lists[pos][idx]\n",
    "        self._delete(pos, idx)\n",
    "        return value\n",
    "\n",
    "    def bisect_left(self, value):\n",
    "        \"\"\"二分查找\"\"\"\n",
    "        pos, idx = self._loc_left(value)\n",
    "        return self._fen_query(pos) + idx\n",
    "\n",
    "    def bisect_right(self, value):\n",
    "        \"\"\"biesect_righ\"\"\"\n",
    "        pos, idx = self._loc_right(value)\n",
    "        return self._fen_query(pos) + idx\n",
    "\n",
    "    def count(self, value):\n",
    "        \"\"\"统计数组中calue有多少个\"\"\"\n",
    "        return self.bisect_right(value) - self.bisect_left(value)\n",
    "\n",
    "    def __len__(self):\n",
    "        \"\"\"Return the size of the sorted list.\"\"\"\n",
    "        return self._len\n",
    "\n",
    "    def __getitem__(self, index):\n",
    "        \"\"\"Lookup value at `index` in sorted list.\"\"\"\n",
    "        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)\n",
    "        return self._lists[pos][idx]\n",
    "\n",
    "    def __delitem__(self, index):\n",
    "        \"\"\"Remove value at `index` from sorted list.\"\"\"\n",
    "        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)\n",
    "        self._delete(pos, idx)\n",
    "\n",
    "    def __contains__(self, value):\n",
    "        \"\"\"Return true if `value` is an element of the sorted list.\"\"\"\n",
    "        _lists = self._lists\n",
    "        if _lists:\n",
    "            pos, idx = self._loc_left(value)\n",
    "            return idx < len(_lists[pos]) and _lists[pos][idx] == value\n",
    "        return False\n",
    "\n",
    "    def __iter__(self):\n",
    "        \"\"\"Return an iterator over the sorted list.\"\"\"\n",
    "        return (value for _list in self._lists for value in _list)\n",
    "\n",
    "    def __reversed__(self):\n",
    "        \"\"\"Return a reverse iterator over the sorted list.\"\"\"\n",
    "        return (value for _list in reversed(self._lists) for value in reversed(_list))\n",
    "\n",
    "    def __repr__(self):\n",
    "        \"\"\"Return string representation of sorted list.\"\"\"\n",
    "        return 'SortedList({0})'.format(list(self))\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: list[int], x: int) -> int:\n",
    "\n",
    "        a = SortedList()\n",
    "        n = len(nums)\n",
    "        res = 1 << 31\n",
    "\n",
    "        for i in range(x, n):\n",
    "            a.add(nums[i-x])\n",
    "            idx = a.bisect_left(nums[i])\n",
    "            if idx<len(a):\n",
    "                res = min(res,abs(a[idx]-nums[i]))\n",
    "            else:\n",
    "                res = min(res,abs(a[-1]-nums[i]))\n",
    "            if idx-1>=0:\n",
    "                res = min(res,abs(a[idx-1]-nums[i]))\n",
    "            if idx+1<len(a):\n",
    "                res = min(res,abs(a[idx+1]-nums[i]))\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        ans = inf\n",
    "        sl = SortedList((-inf,inf)) # 哨兵\n",
    "        for v, y in zip(nums,nums[x:]):\n",
    "            sl.add(v)\n",
    "            j = sl.bisect_left(y)\n",
    "            ans = min(ans, sl[j]-y, y-sl[j-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], k: int) -> int:\n",
    "        ans = inf \n",
    "        sl = SortedList([-inf, inf]) \n",
    "        for x, y in zip(nums, nums[k:]) : \n",
    "            sl.add(x) \n",
    "            j = sl.bisect_left(y) \n",
    "            ans = min(ans, sl[j] - y, y - sl[j - 1]) \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        ans = inf\n",
    "        sl = SortedList((-inf, inf))  # 哨兵\n",
    "        for v, y in zip(nums, nums[x:]):\n",
    "            sl.add(v)\n",
    "            j = sl.bisect_left(y)\n",
    "            ans = min(ans, sl[j] - y, y - sl[j - 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        ctn = SortedList((-inf, inf))\n",
    "        res = inf\n",
    "        for x, y in zip(nums, nums[x:]):\n",
    "            ctn.add(x)\n",
    "            index = ctn.bisect_left(y)\n",
    "            res = min(res, ctn[index]-y, y-ctn[index-1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        st = SortedList([-inf, inf])\n",
    "        res = inf\n",
    "        for x, y in zip(nums, nums[x:]):\n",
    "            st.add(x)\n",
    "            pos = st.bisect_left(y) # pos 是第一个 >= 的数\n",
    "            res = min(res, st[pos]-y, y-st[pos-1])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        ans = inf\n",
    "        sl = SortedList((-inf, inf))\n",
    "        \n",
    "        def getminbig(x):\n",
    "            l, r = 0, len(sl)\n",
    "            while l < r:\n",
    "                mid = l + r >> 1\n",
    "                if sl[mid] >= x:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            return l\n",
    "        \n",
    "\n",
    "        ans = inf\n",
    "        for v, y in zip(nums, nums[x:]):\n",
    "            sl.add(v)\n",
    "            idx = getminbig(y)\n",
    "            ans = min(ans, sl[idx] - y, y - sl[idx-1])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        if x == 0:\n",
    "            return 0\n",
    "        ans = inf\n",
    "        sl = SortedList((-inf, inf))\n",
    "        for v, y in zip(nums, nums[x:]):\n",
    "            sl.add(v)\n",
    "            j = sl.bisect_left(y)\n",
    "            ans = min(ans, y-sl[j-1], sl[j]-y )\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        ans = inf\n",
    "        sl = SortedList((-inf, inf))\n",
    "\n",
    "        def getminbig(x, ls):\n",
    "            l, r = 0, len(ls)-1\n",
    "            while l < r:\n",
    "                mid = l + r >> 1\n",
    "                if ls[mid] >= x:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            return l\n",
    "        \n",
    "        for x, y in zip(nums, nums[x:]):\n",
    "            sl.add(x)\n",
    "            idx = getminbig(y, sl)\n",
    "            ans = min(ans, sl[idx] - y, y - sl[idx - 1])\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        ans = inf\n",
    "        sl = SortedList((-inf, inf))  # 哨兵\n",
    "        for v, y in zip(nums, nums[x:]):\n",
    "            sl.add(v)\n",
    "            j = sl.bisect_left(y)\n",
    "            ans = min(ans, sl[j] - y, y - sl[j - 1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        inf = 9999999999999999999\n",
    "        ans = inf\n",
    "        sl = SortedList((-inf, inf))  # 哨兵\n",
    "        for v, y in zip(nums, nums[x:]):\n",
    "            sl.add(v)\n",
    "            j = sl.bisect_left(y)\n",
    "            ans = min(ans, sl[j] - y, y - sl[j - 1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        ans = inf\n",
    "        sl = SortedList((-inf, inf))\n",
    "        \n",
    "        def getminbig(x):\n",
    "            l, r = 0, len(sl)\n",
    "            while l < r:\n",
    "                mid = l + r >> 1\n",
    "                if sl[mid] >= x:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            return sl[l]\n",
    "        \n",
    "        def getmaxsmall(x):\n",
    "            l, r = 0, len(sl)\n",
    "            while l < r:\n",
    "                mid = l + r + 1 >> 1\n",
    "                if sl[mid] <= x:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            return sl[l]\n",
    "\n",
    "        ans = inf\n",
    "        for v, y in zip(nums, nums[x:]):\n",
    "            sl.add(v)\n",
    "            ans = min(ans, getminbig(y) - y, y - getmaxsmall(y))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        # 枚举\n",
    "        ans = inf\n",
    "        s1 = SortedList([-inf,inf])\n",
    "        for x,y in zip(nums,nums[x:]):\n",
    "            s1.add(x)\n",
    "            j = s1.bisect_left(y)\n",
    "            ans = min(ans,s1[j]-y,y-s1[j-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        s = SortedList((-inf, inf))\n",
    "        ans = inf\n",
    "        for v, y in zip(nums, nums[x:]):\n",
    "            s.add(v)\n",
    "            i = bisect.bisect_left(s, y)\n",
    "            ans = min(ans, s[i] - y, y - s[i - 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        ans = inf\n",
    "        sl = SortedList((-inf, inf))\n",
    "        \n",
    "        def getminbig(x):\n",
    "            l, r = 0, len(sl)\n",
    "            while l < r:\n",
    "                mid = l + r >> 1\n",
    "                if sl[mid] >= x:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            return l\n",
    "        \n",
    "\n",
    "        ans = inf\n",
    "        for v, y in zip(nums, nums[x:]):\n",
    "            sl.add(v)\n",
    "            idx = getminbig(y)\n",
    "            ans = min(ans, sl[idx] - y, y - sl[idx-1])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution(object):\n",
    "    def minAbsoluteDifference(self, nums, x):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type x: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if x==0:\n",
    "            return 0\n",
    "        x=x-1\n",
    "        m=10**9\n",
    "        L=SortedList(nums[x:])\n",
    "        for i in range(len(nums)-x-1):\n",
    "            L.discard(nums[i+x])\n",
    "            a=L.bisect_left(nums[i])\n",
    "            if a!=0:\n",
    "                m=min(m,abs(nums[i]-L[a-1]))\n",
    "            if a!=len(L):\n",
    "                m=min(m,abs(nums[i]-L[a]))\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "固定右端点\n",
    "求abs  二分  需要一个下标递增，值也递增的结构（没办法）\n",
    "\n",
    "直接双指针，用平衡树的话，共有n*logn次插入，每次查询需要logn的时间，共有n次查询\n",
    "'''\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        ans=inf\n",
    "        sl=SortedList((-inf,inf))\n",
    "        for v,y in zip(nums,nums[x:]):\n",
    "            sl.add(v)\n",
    "            j=sl.bisect_left(y)\n",
    "            ans=min(ans,sl[j]-y,y-sl[j-1])\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        ans = inf\n",
    "        sl = SortedList((-inf, inf))\n",
    "        for v,y in zip(nums,nums[x:]):\n",
    "            sl.add(v)\n",
    "            j = sl.bisect_left(y)\n",
    "            ans = min(ans, sl[j] - y, y - sl[j - 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], k: int) -> int:\n",
    "        ans = inf\n",
    "        sl = SortedList([-inf, inf])\n",
    "        for x, y in zip(nums, nums[k:]):\n",
    "            sl.add(x)\n",
    "            j = sl.bisect_left(y)\n",
    "            ans = min(ans, sl[j] - y, y - sl[j - 1])\n",
    "        return ans\n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        a = sorted(nums)\n",
    "        ans = inf\n",
    "        arr = SortedList(nums[x:n])\n",
    "\n",
    "\n",
    "        def findClosestNumber( sorted_list: SortedList[int], x: int) -> int:\n",
    "            index = sorted_list.bisect_left(x)  # Find the insertion index for x\n",
    "\n",
    "            if index == 0:\n",
    "                return abs(sorted_list[0] - x)\n",
    "            elif index == len(sorted_list):\n",
    "                return abs(sorted_list[-1] - x)\n",
    "            else:\n",
    "                diff_before = abs(sorted_list[index - 1] - x)\n",
    "                diff_after = abs(sorted_list[index] - x)\n",
    "\n",
    "                return min(diff_before, diff_after)\n",
    "            \n",
    "        for i in range(n - x):\n",
    "            ans = min(ans,findClosestNumber(arr,nums[i]))\n",
    "            arr.remove(nums[i +x])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], k: int) -> int:\n",
    "        ans = inf\n",
    "        sl = SortedList([-inf, inf])  # 哨兵\n",
    "        for x, y in zip(nums, nums[k:]):\n",
    "            sl.add(x)\n",
    "            j = sl.bisect_left(y)\n",
    "            print(j)\n",
    "            ans = min(ans, sl[j] - y, y - sl[j - 1])\n",
    "        return ans\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], k: int) -> int:\n",
    "        ans = inf\n",
    "        sl = SortedList([-inf, inf])  # 哨兵\n",
    "\n",
    "        print(zip(nums, nums[k:]))\n",
    "        for x, y in zip(nums, nums[k:]):\n",
    "\n",
    "            print(x, y)\n",
    "            sl.add(x)\n",
    "            j = sl.bisect_left(y)\n",
    "            ans = min(ans, sl[j] - y, y - sl[j - 1])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], k: int) -> int:\n",
    "        ans = inf\n",
    "        sl = SortedList([-inf, inf])  # 哨兵\n",
    "\n",
    "\n",
    "        for x, y in zip(nums, nums[k:]):\n",
    "\n",
    "            print(x, y)\n",
    "            sl.add(x)\n",
    "            j = sl.bisect_left(y)\n",
    "            ans = min(ans, sl[j] - y, y - sl[j - 1])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        ans = inf\n",
    "        sl = SortedList((-inf, inf))  # 哨兵\n",
    "\n",
    "        for v, y in zip(nums, nums[x:]):\n",
    "            print(v,y)\n",
    "            sl.add(v)\n",
    "            j = sl.bisect_left(y)\n",
    "\n",
    "            ans = min(ans, sl[j] - y, y - sl[j - 1])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        if x==0:\n",
    "            return 0\n",
    "      \n",
    "        n=len(nums)\n",
    "        frontd=[nums[0]]\n",
    "        fset=set([nums[0]])\n",
    "       \n",
    "        ans=abs(nums[0]-nums[n-1])\n",
    "    \n",
    "        for i in range(x,n):\n",
    "            bi=bisect.bisect_left(frontd,nums[i])\n",
    "            if bi==len(frontd):\n",
    "                gap=nums[i]-frontd[-1]\n",
    "                if gap<ans:\n",
    "                    ans=gap\n",
    "            else:\n",
    "                gap=frontd[bi]-nums[i]\n",
    "                if bi-1>=0:\n",
    "                    gap=min(gap,nums[i]-frontd[bi-1])\n",
    "                if gap<ans:\n",
    "                    ans=gap\n",
    "            nn=nums[i-x+1]\n",
    "            if nn not in fset:\n",
    "                fset.add(nn)\n",
    "                bisect.insort(frontd,nn)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "from typing import List\n",
    "\n",
    "from sortedcontainers import SortedSet\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, a: List[int], x: int) -> int:\n",
    "        ans = float('inf')\n",
    "        s = SortedSet()\n",
    "        n = len(a)\n",
    "        for i in range(x, n):\n",
    "            s.add(a[i - x])\n",
    "            idx = bisect_left(s, a[i])\n",
    "            if idx < len(s):\n",
    "                ans = min(ans, abs(a[i] - s[idx]))\n",
    "            if idx > 0:\n",
    "                ans = min(ans, abs(a[i] - s[idx - 1]))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedSet\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        if x == 0: return 0\n",
    "        n = len(nums)\n",
    "        ans = math.inf\n",
    "        s = SortedSet()\n",
    "        l = -1\n",
    "        for r in range(x, n):\n",
    "            l += 1\n",
    "            s.add(nums[l])\n",
    "            i = s.bisect_left(nums[r])\n",
    "            if i < len(s): ans = min(ans, s[i] - nums[r])\n",
    "            if i > 0: ans = min(ans, nums[r] - s[i - 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedSet\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        sl = SortedSet()\n",
    "        diff = 1000000000\n",
    "        for i, v in enumerate(nums):\n",
    "            if i>=x:\n",
    "                sl.add(nums[i-x])\n",
    "            l = sl.bisect(nums[i])\n",
    "            if (l != len(sl)):\n",
    "                diff = min(diff, abs(nums[i]-sl[l]))\n",
    "            if (l >0):\n",
    "                diff = min(diff, abs(nums[i]-sl[l-1]))\n",
    "#            print(i, v, sl, l, diff)\n",
    "        return diff;\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedSet\n",
    "\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        ss = SortedSet()\n",
    "        n = len(nums)\n",
    "        ans = float('inf')\n",
    "        for i in range(x, n):\n",
    "            ss.add(nums[i - x])\n",
    "            index = ss.bisect_left(nums[i])\n",
    "            if index < len(ss):\n",
    "                ans = min(ans, abs(nums[i] - ss[index]))\n",
    "            if index - 1 >= 0:\n",
    "                ans = min(ans, abs(nums[i] - ss[index - 1]))\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedSet\n",
    "class Solution:\n",
    "    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:\n",
    "        n = len(nums)\n",
    "        ss = SortedSet((-inf, inf))\n",
    "        ret = inf\n",
    "\n",
    "        for i in range(x, n):\n",
    "            ss.add(nums[i-x])\n",
    "            j = ss.bisect_left(nums[i])\n",
    "            ret = min(ret, ss[j] - nums[i], nums[i] - ss[j-1])\n",
    "        \n",
    "        return ret"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
